package LeetCode.Leet700_799.Leet760_769.Leet763;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution_2
 * @Author 孙天赐
 * @Date 2025/5/31 13:36
 * @Description TODO: 方法二  模拟（贪心）优化  2ms    99.26%
 *                  相比方法一，在方法一中，我们每次都要从后往前找到该字符最后出现的位置，性能较低
 *                  该方法直接通过一个数组来记录每个字符最后出现的位置，提高性能
 */
class Solution_2 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> result = new ArrayList<>();
        char[] sArr = s.toCharArray();  // 转化为数组效率更高

        // 记录每个字母最后一次出现的位置
        int[] indexArr = new int[26];
        for (int i = 0; i < sArr.length; i++) {
            if (indexArr[sArr[i] - 'a'] < i) {
                indexArr[sArr[i] - 'a'] = i;
            }
        }

        int startIndex = 0;  // 当前切分的起始位置
        int endIndex = 0;  // 当前切分的终止位置
        int i = 0;  // 当前循环判断的元素
        while (endIndex < sArr.length) {
            char c = sArr[i];
            // 找到该字母最后一次出现的位置，并更新endIndex
            endIndex = Math.max(endIndex, indexArr[sArr[i] - 'a']);
            // 如果i到达了最终截取的位置，则截取
            if (i == endIndex) {
                result.add(endIndex - startIndex + 1);
                endIndex++;
                startIndex = endIndex;
            }
            i++;
        }

        return result;
    }
}
